home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / graph.h < prev    next >
Encoding:
C/C++ Source or Header  |  1992-06-05  |  24.0 KB  |  729 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  graph.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef GRAPHH
  17. #define GRAPHH
  18.  
  19. /*------------------------------------------------------------------------------
  20.  
  21.     Graph
  22.  
  23.     Stefan Naeher
  24.     FB10 Informatik 
  25.     Universitaet des Saarlandes 
  26.     6600 Saarbruecken
  27.  
  28.     September 1988
  29.     
  30. ------------------------------------------------------------------------------*/
  31.  
  32.  
  33. #include <LEDA\basic.h>
  34. #include <LEDA\list.h>
  35.  
  36.  
  37. //------------------------------------------------------------------------------
  38. /* declare node, edge, list(node) and list(edge)                              */
  39. //------------------------------------------------------------------------------
  40.  
  41. class i_node;
  42. class i_edge;
  43.  
  44. // node = pointer to internal node
  45. typedef i_node* node;
  46.  
  47. // edge = pointer to internal edge
  48. typedef i_edge* edge;
  49.  
  50.  
  51. /* nodelist = doubly linked list of nodes */
  52. declare(list,node)
  53.  
  54. /* list(edge) = doubly linked list of edges */
  55. declare(list,edge)
  56.  
  57.  
  58.  
  59. //------------------------------------------------------------------------------
  60. // class i_node: internal representation of nodes
  61. //------------------------------------------------------------------------------
  62.  
  63. class i_node {  
  64.  
  65.    friend class graph;
  66.    friend class ugraph;
  67.    friend class planar_map;
  68.    
  69.    friend graph* graph_of(edge);
  70.  
  71.    graph* g;             // pointer to graph 
  72.    int i_name;           // internal name (index)  
  73.    list_item loc;        // location in V
  74.    int indegree;        
  75.    ent contents;         // user defined pointer-type
  76.    list(edge) adj_edges;   /* list of adjacent edges */ 
  77.  
  78.    i_node(ent i)
  79.    { 
  80.      contents=i;
  81.      i_name = -1; 
  82.      g = 0; 
  83.      loc = 0; 
  84.      indegree = 0;
  85.    }
  86.  
  87.    OPERATOR_NEW(10)  
  88.    OPERATOR_DEL(10)
  89.  
  90. friend graph* graph_of(node v)   { return v->g;         }
  91. friend int    indeg(node v)      { return v->indegree;  }
  92. friend int    outdeg(node v)     { return v->adj_edges.length(); }
  93. friend int    degree(node v)     { return v->adj_edges.length(); }
  94. friend int    index(node v)      { return v->i_name;    }
  95.  
  96. /* space :  5 words + 1 list = 20 + 20 bytes = 40 bytes */
  97. };
  98.  
  99.  
  100. //------------------------------------------------------------------------------
  101. // class i_edge: internal representation of edges
  102. //------------------------------------------------------------------------------
  103.  
  104. class i_edge { 
  105.    
  106.    friend class graph;
  107.    friend class ugraph;
  108.    friend class planar_map;
  109.  
  110.    friend graph* graph_of(edge);
  111.  
  112.    int i_name;           // internal name (index)  
  113.    node s;               // edge from "source" 
  114.    node t;               // to "target"
  115.    list_item loc;        // location in |E|
  116.    list_item adj_loc;    // location in adjacencylist of source(e)
  117.    list_item adj_loc2;   // location in adjacencylist of target(e) (ugraph)
  118.    ent contents;         // user defined pointer type
  119.  
  120.    i_edge(node v, node w, ent i)
  121.    { contents=i;
  122.      i_name=-1;
  123.      s=v;
  124.      t=w;
  125.      loc=0;
  126.      adj_loc=0;
  127.      adj_loc2=0;
  128.    }
  129.  
  130.    OPERATOR_NEW(7)  
  131.    OPERATOR_DEL(7)
  132.  
  133. friend node   source(edge e) { return e->s;         }
  134. friend node   target(edge e) { return e->t;         }
  135. friend int    index(edge e)  { return e->i_name;    }
  136.  
  137. //space :  7 words = 28 bytes
  138. };
  139.  
  140.  
  141. inline graph* graph_of(edge e)   { return e->s->g;      }
  142.  
  143.  
  144.  
  145. typedef int  (*COMPARE(graph,node)) (node&, node&);
  146. typedef int  (*COMPARE(graph,edge)) (edge&, edge&);
  147.  
  148.  
  149. //------------------------------------------------------------------------------
  150. // Macro zur Definition von Feldern mit Indextyp node oder edge
  151. //------------------------------------------------------------------------------
  152.  
  153. // declaration (itype = node/edge):
  154.  
  155. #define graph_array(itype) name2(itype,graph_array)
  156.  
  157. #define graph_arraydeclare(itype)\
  158. \
  159. class graph_array(itype) {\
  160. graph* g;  /* array is declared for graph *g */  \
  161. int max_i; /* maximal node index in g at declaration time */  \
  162. ent* arr;  \
  163. virtual void clear_entry(ent& x) const { x=0; }\
  164. virtual void copy_entry(ent& x)  const { x=x; }\
  165. virtual void init_entry(ent& x)  const { x=0; }\
  166. \
  167. public:\
  168. virtual int cmp_entry(itype x, itype y) const { return int(inf(x))-int(inf(y)); }\
  169. \
  170.  ent& entry(itype);\
  171.  ent  inf(itype) const;\
  172.  void init(const graph&, int, ent);\
  173.  void init(const graph&, ent);\
  174.  void init(const graph_array(itype)&);\
  175.  void clear();\
  176.  ent& elem(int i)                    { return arr[i]; }\
  177.  int  size()               const     { return max_i+1;}\
  178.  graph_array(itype)()                { g=0; max_i=(-1); arr=0;}\
  179. ~graph_array(itype)()                { clear(); }\
  180. };\
  181.  
  182.  
  183. declare(graph_array,node)
  184. declare(graph_array,edge)
  185.  
  186.  
  187. //------------------------------------------------------------------------------
  188. // graph: base class for all graphs
  189. //------------------------------------------------------------------------------
  190.  
  191. class graph {
  192.  
  193. friend class ugraph;
  194. friend class planar_map;
  195.  
  196. list(node) V;              /* list of all nodes */
  197. list(edge) E;              /* list of all edges */
  198.  
  199. int max_node_index;      // maximal node index 
  200. int max_edge_index;      // maximal edge index
  201.  
  202. graph* parent;           // for subgraphs
  203.  
  204. bool   undirected;       // true iff graph undirected
  205.  
  206. /* space: 2 lists + 4 words + "virtual" = 2*20 + 5*4 bytes = 60 bytes */
  207.  
  208. virtual void init_node_entry(ent& x)  const { x=0; }
  209. virtual void init_edge_entry(ent& x)  const { x=0; }
  210.  
  211. virtual void copy_node_entry(ent& x)  const { x=x; }
  212. virtual void copy_edge_entry(ent& x)  const { x=x; }
  213.  
  214. virtual void clear_node_entry(ent& x) const { x=0; }
  215. virtual void clear_edge_entry(ent& x) const { x=0; }
  216.  
  217. virtual void read_node_entry(istream& in, ent& x)  const { Read(int(x),in); }
  218. virtual void read_edge_entry(istream& in, ent& x)  const { Read(int(x),in); }
  219.  
  220. virtual void write_node_entry(ostream& o, ent& x)  const { Print(int(x),o); }
  221. virtual void write_edge_entry(ostream& o, ent& x)  const { Print(int(x),o); }
  222.  
  223. virtual void print_node_entry(ostream&, ent&)  const {}
  224. virtual void print_edge_entry(ostream&, ent&)  const {}
  225.  
  226. virtual string node_type()  const { return "void"; }
  227. virtual string edge_type()  const { return "void"; }
  228.  
  229. protected:
  230.  
  231. void copy_all_entries();
  232.  
  233. public:
  234.  
  235. virtual int cmp_node_entry(node, node) const { return 0; }
  236. virtual int cmp_edge_entry(edge, edge) const { return 0; }
  237.  
  238.    int  space() const;
  239.    list(node) adj_nodes(node)   const;
  240.    void reset() const;
  241.  
  242.  
  243.    int  indeg(node v)     const;
  244.    int  outdeg(node v)    const;
  245.    node source(edge e)    const;
  246.    node target(edge e)    const;
  247.  
  248.    graph* super()         const;
  249.    int max_node_i()       const;
  250.    int max_edge_i()       const;
  251.  
  252.    int  number_of_nodes() const;
  253.    int  number_of_edges() const;
  254.  
  255.    list(node) all_nodes()       const;
  256.    list(edge) all_edges()       const;
  257.    list(edge) adj_edges(node v) const;
  258.  
  259.    ent& entry(node v);
  260.    ent& entry(edge e);
  261.    ent  inf(node v) const;
  262.    ent  inf(edge e) const;
  263.  
  264.    void assign(node v,ent x);
  265.    void assign(edge e,ent x);
  266.  
  267.  
  268.    void init_node_iterator() const;
  269.    void init_edge_iterator() const;
  270.    int  next_node(node& v)   const;
  271.    int  prev_node(node& v)   const;
  272.    int  next_edge(edge& e)   const;
  273.    int  prev_edge(edge& e)   const;
  274.  
  275.    edge first_adj_edge(node v)  const;
  276.    edge last_adj_edge(node v)   const;
  277.  
  278.    void init_adj_iterator(node v)        const;
  279.    int  next_adj_edge(edge& e,node v)    const ;
  280.    int  current_adj_edge(edge& e,node v) const ;
  281.    int  next_adj_node(node& w,node v)    const;
  282.    int  current_adj_node(node& w,node v) const;
  283.    
  284.    node first_node()      const;
  285.    edge first_edge()      const;
  286.    node last_node()       const;
  287.    edge last_edge()       const;
  288.    node choose_node()     const;
  289.    edge choose_edge()     const;
  290.    node succ_node(node v) const;
  291.    node pred_node(node v) const;
  292.    edge succ_edge(edge e) const;
  293.    edge pred_edge(edge e) const;
  294.    edge adj_succ(edge e)  const;
  295.    edge adj_pred(edge e)  const;
  296.    edge cyclic_adj_succ(edge e) const;
  297.    edge cyclic_adj_pred(edge e) const;
  298.  
  299.  
  300.    node new_node(ent);
  301.    void del_node(node);
  302.    void del_edge(edge);
  303.    edge new_edge(node, node, ent);
  304.    edge new_edge(edge, node, ent, int dir);
  305.  
  306.    node new_node()   { ent x; init_node_entry(x);  
  307.                        return new_node(x); }
  308.  
  309.    edge new_edge(node v, node w) 
  310.    { ent x; init_edge_entry(x);
  311.      return new_edge(v,w,x);}
  312.  
  313.    edge new_edge(edge e, node w, int dir=0) 
  314.    { ent x; init_edge_entry(x);
  315.      return new_edge(e,w,x,dir); }
  316.  
  317.  
  318.    void del_all_nodes(); 
  319.    void del_all_edges(); 
  320.  
  321.    list(edge) insert_reverse_edges();
  322.  
  323.    void sort_edges(COMPARE(graph,edge));
  324.    void sort_nodes(COMPARE(graph,node));
  325.  
  326.    void sort_edges(const graph_array(edge)&);
  327.    void sort_nodes(const graph_array(node)&);
  328.  
  329.    void sort_edges();
  330.    void sort_nodes();
  331.  
  332.    edge rev_edge(edge);
  333.    graph& rev();
  334.  
  335.    void make_directed();
  336.    void make_undirected();
  337.  
  338.    void write(string s) const;
  339.    int  read (string s);
  340.  
  341.    void print_node(node,ostream& = cout)  const;
  342.  
  343. virtual void print_edge(edge,ostream& = cout)  const;  //different for ugraph's
  344.  
  345.    void print(string s, ostream& = cout) const;
  346.  
  347.    void print()           const { print("");   }
  348.    void print(ostream& o) const { print("",o); }
  349.  
  350.    void clear();
  351.  
  352.    graph();
  353.    graph(const graph&);
  354.    graph& operator=(const graph&); 
  355.  
  356.   ~graph() { clear(); }
  357.  
  358.  
  359.    //subgraph constructors
  360.  
  361.    graph(graph&, list(node)&, list(edge)&);
  362.    graph(graph&, list(edge)&);
  363.  
  364. };
  365.  
  366. inline int  graph::indeg(node v)     const   { return v->indegree; }
  367. inline int  graph::outdeg(node v)    const   { return v->adj_edges.length(); }
  368. inline node graph::source(edge e)    const   { return e->s; }
  369. inline node graph::target(edge e)    const   { return e->t; }
  370.  
  371. inline graph* graph::super()         const   { return parent; }
  372. inline int graph::max_node_i()       const   { return max_node_index; }
  373. inline int graph::max_edge_i()       const   { return max_edge_index; }
  374.  
  375. inline int  graph::number_of_nodes() const   { return V.length(); }
  376. inline int  graph::number_of_edges() const   { return E.length(); }
  377.  
  378. inline ent& graph::entry(node v)        { return v->contents; }
  379. inline ent& graph::entry(edge e)        { return e->contents; }
  380. inline void graph::assign(node v,ent x) { v->contents = x; }
  381. inline void graph::assign(edge e,ent x) { e->contents = x; }
  382.  
  383. inline ent  graph::inf(node v) const { return v->contents; }
  384. inline ent  graph::inf(edge e) const { return e->contents; }
  385.  
  386.  
  387. inline void graph::init_node_iterator()   const { V.init_iterator(); }
  388. inline void graph::init_edge_iterator()   const { E.init_iterator(); }
  389. inline int  graph::next_node(node& v)     const { return V.next_element(v); }
  390. inline int  graph::prev_node(node& v)     const { return V.prev_element(v); }
  391. inline int  graph::next_edge(edge& e)     const { return E.next_element(e); }
  392. inline int  graph::prev_edge(edge& e)     const { return E.prev_element(e); }
  393. inline edge graph::first_adj_edge(node v) const { return v->adj_edges.head(); }
  394. inline edge graph::last_adj_edge(node v)  const { return v->adj_edges.tail(); }
  395.  
  396.  
  397. inline void graph::init_adj_iterator(node v) const 
  398. { v->adj_edges.init_iterator(); }
  399.  
  400. inline int  graph::next_adj_edge(edge& e,node v) const 
  401. { return v->adj_edges.next_element(e); }
  402.  
  403. inline int  graph::current_adj_edge(edge& e,node v) const 
  404. { return v->adj_edges.current_element(e);}
  405.  
  406.  
  407. inline int graph::next_adj_node(node& w,node v)  const
  408. { edge e;
  409.   if (next_adj_edge(e,v))
  410.   { w = (v==e->s) ? e->t : e->s;
  411.     return 1; 
  412.    }
  413.   else { w = 0; return 0;}
  414.  }
  415.    
  416. inline int graph::current_adj_node(node& w,node v)  const
  417. { edge e;
  418.   if (current_adj_edge(e,v))
  419.   { w = (v==e->s) ? e->t : e->s; 
  420.     return 1; }
  421.   else { w = 0; return 0; }
  422. }
  423.    
  424. inline node graph::first_node()   const { return V.head(); }
  425. inline edge graph::first_edge()   const { return E.head(); }
  426. inline node graph::last_node()    const { return V.tail(); }
  427. inline edge graph::last_edge()    const { return E.tail(); }
  428. inline node graph::choose_node()  const { return V.head(); }
  429. inline edge graph::choose_edge()  const { return E.head(); }
  430.  
  431. inline node graph::succ_node(node v)  const  
  432. { list_item loc = V.succ(v->loc);
  433.   return (loc) ? V.inf(loc) : 0;
  434.  }
  435.  
  436. inline node graph::pred_node(node v)  const  
  437. { list_item loc = V.pred(v->loc);
  438.   return (loc) ? V.inf(loc) : 0;
  439.  }
  440.  
  441. inline edge graph::succ_edge(edge e)  const  
  442. { list_item loc = E.succ(e->loc);
  443.   return (loc) ? E.inf(loc) : 0;
  444.  }
  445.  
  446. inline edge graph::pred_edge(edge e)  const  
  447. { list_item loc = E.pred(e->loc);
  448.   return (loc) ? E.inf(loc) : 0;
  449.  }
  450.  
  451.  
  452. inline edge graph::adj_succ(edge e) const 
  453. { list_item loc = e->s->adj_edges.succ(e->adj_loc);
  454.   return (loc) ? e->s->adj_edges[loc] : 0; 
  455.  } 
  456.  
  457. inline edge graph::adj_pred(edge e) const 
  458. { list_item loc = e->s->adj_edges.pred(e->adj_loc);
  459.   return (loc) ? e->s->adj_edges[loc] : 0; 
  460.  } 
  461.  
  462. inline edge graph::cyclic_adj_succ(edge e) const 
  463. { list_item loc = e->s->adj_edges.cyclic_succ(e->adj_loc);
  464.   return e->s->adj_edges[loc];
  465.  }
  466.  
  467. inline edge graph::cyclic_adj_pred(edge e)  const
  468. { list_item loc = e->s->adj_edges.cyclic_pred(e->adj_loc);
  469.   return e->s->adj_edges[loc];
  470.  }
  471.  
  472.  
  473.  
  474. //------------------------------------------------------------------------------
  475. // GRAPH: generic directed graphs
  476. //------------------------------------------------------------------------------
  477.  
  478. #define GRAPH(vtype,etype)   name3(vtype,etype,GRAPH)
  479.  
  480. #define GRAPHdeclare2(vtype,etype)\
  481. class GRAPH(vtype,etype) : public graph {\
  482. \
  483. void init_node_entry(ent& x) const  { x = Copy(vtype(0)); }\
  484. void init_edge_entry(ent& x) const  { x = Copy(etype(0)); }\
  485. \
  486. void copy_node_entry(ent& x) const  { Copy(*(vtype*)&x); }\
  487. void copy_edge_entry(ent& x) const  { Copy(*(etype*)&x); }\
  488. \
  489. void clear_node_entry(ent& x) const { Clear(*(vtype*)&x); }\
  490. void clear_edge_entry(ent& x) const { Clear(*(etype*)&x); }\
  491. \
  492. void read_node_entry(istream& i, ent& x)  const { Read(*(vtype*)&x,i); }\
  493. void read_edge_entry(istream& i, ent& x)  const { Read(*(etype*)&x,i); }\
  494. \
  495. void write_node_entry(ostream& o, ent& x)  const { Print(*(vtype*)&x,o); }\
  496. void write_edge_entry(ostream& o, ent& x)  const { Print(*(etype*)&x,o); }\
  497. \
  498. void print_node_entry(ostream& o, ent& x)  const\
  499.      { o << "("; Print(*(vtype*)&x,o); o << ")"; }\
  500. void print_edge_entry(ostream& o, ent& x)  const\
  501.      { o << "("; Print(*(etype*)&x,o); o << ")"; }\
  502. \
  503. string node_type()  const { return STRINGIZE(vtype); }\
  504. string edge_type()  const { return STRINGIZE(etype); }\
  505. \
  506. public:\
  507. \
  508. int cmp_node_entry(node x, node y) const { return compare(inf(x),inf(y)); }\
  509. int cmp_edge_entry(edge x, edge y) const { return compare(inf(x),inf(y)); }\
  510. \
  511.    vtype  inf(node v)    const   { return vtype(graph::inf(v)); }\
  512.    etype  inf(edge e)    const   { return etype(graph::inf(e)); }\
  513.    vtype& operator[] (node v)         { return *(vtype*)&graph::entry(v); }\
  514.    vtype  operator[] (node v) const   { return vtype(graph::inf(v)); }\
  515.    etype& operator[] (edge e)         { return *(etype*)&graph::entry(e); }\
  516.    etype  operator[] (edge e) const   { return etype(graph::inf(e)); }\
  517.    void   assign(node v,vtype x) { graph::assign(v,Ent(x)); }\
  518.    void   assign(edge e,etype x) { graph::assign(e,Ent(x)); }\
  519.    node   new_node()             { return graph::new_node(); }\
  520.    node   new_node(vtype a)      { return graph::new_node(Copy(a)); }\
  521.    edge   new_edge(node v, node w)\
  522.                               { return graph::new_edge(v,w); }\
  523.    edge   new_edge(node v, node w, etype a)\
  524.                               { return graph::new_edge(v,w,Copy(a)); }\
  525.    edge   new_edge(edge e, node w)\
  526.                               { return graph::new_edge(e,w); }\
  527.    edge   new_edge(edge e, node w, etype a)\
  528.                               { return graph::new_edge(e,w,Copy(a),0); }\
  529.    edge   new_edge(edge e, node w, etype a, int dir)\
  530.                               { return graph::new_edge(e,w,Copy(a),dir); }\
  531. \
  532.    GRAPH(vtype,etype)& operator=(const GRAPH(vtype,etype)& a)\
  533.        {return (GRAPH(vtype,etype)&)(graph::operator=((graph&)a)); }\
  534.    GRAPH(vtype,etype)()     {}\
  535.    GRAPH(vtype,etype)(const GRAPH(vtype,etype)& a) : graph((graph&)a) { copy_all_entries();} \
  536. /* sub graphs */\
  537.    GRAPH(vtype,etype)(GRAPH(vtype,etype)& a, list(node)& b, list(edge)& c)\
  538.                                                 : graph((graph&)a,b,c) {}\
  539.    GRAPH(vtype,etype)(GRAPH(vtype,etype)& a, list(edge)& c)\
  540.                                                 : graph((graph&)a,c) {}\
  541.    ~GRAPH(vtype,etype)()     { clear(); }\
  542. };
  543.  
  544. //------------------------------------------------------------------------------
  545. // node arrays
  546. //------------------------------------------------------------------------------
  547.  
  548. #define node_array(TYPE) name2(TYPE,node_array)
  549.  
  550. #define node_arraydeclare(type)\
  551. \
  552. class node_array(type) : public graph_array(node) {\
  553. void copy_entry(ent& x)  const { x = Copy(*(type*)&x);  }\
  554. void clear_entry(ent& x) const { Clear(*(type*)&x);     }\
  555. void init_entry(ent& x)  const { x = Copy(type(0)); }\
  556. \
  557. public:\
  558. int cmp_entry(node x,node y) const { return compare(operator[](x),operator[](y)); }\
  559. \
  560. type& operator[](node x)       { return *(type*)&graph_array(node)::entry(x);}\
  561. type  operator[](node x) const { return type(graph_array(node)::inf(x));}\
  562. type& elem(int i)           { return *(type*)&graph_array(node)::elem(i);}\
  563. void  init(const graph& G, int n, type i)\
  564.                                   { graph_array(node)::init(G,n,Ent(i)); }\
  565. void  init(const graph& G, type i){ graph_array(node)::init(G,Ent(i)); }\
  566. void  init(const graph& G)  { type y=0; graph_array(node)::init(G,Ent(y)); }\
  567. void  init(const node_array(type)& A)\
  568.                             { graph_array(node)::init((graph_array(node)&) A); }\
  569. \
  570. node_array(type)()                                 {}\
  571. node_array(type)(const graph& G)                   { init(G);   }\
  572. node_array(type)(const graph& G, int n, type i)    { init(G,n,i); }\
  573. node_array(type)(const graph& G, type i)           { init(G,i); }\
  574. node_array(type)(const node_array(type)& A)        { init(A);   }\
  575. node_array(type)& operator=(const node_array(type)& A) { init(A); return *this;}\
  576. \
  577. ~node_array(type)()                { clear(); }\
  578. };
  579.  
  580.  
  581. //------------------------------------------------------------------------------
  582. // edge arrays
  583. //------------------------------------------------------------------------------
  584.  
  585. #define edge_array(TYPE) name2(TYPE,edge_array)
  586.  
  587. #define edge_arraydeclare(type)\
  588. \
  589. class edge_array(type) : public graph_array(edge) {\
  590. void copy_entry(ent& x)  const { x = Copy(*(type*)&x);  }\
  591. void clear_entry(ent& x) const { Clear(*(type*)&x);     }\
  592. void init_entry(ent& x)  const { x = Copy(type(0)); }\
  593. \
  594. public:\
  595. int cmp_entry(edge x,edge y) const { return compare(operator[](x),operator[](y)); }\
  596. \
  597. type& operator[](edge x)       { return *(type*)&graph_array(edge)::entry(x);}\
  598. type  operator[](edge x) const { return type(graph_array(edge)::inf(x));}\
  599. type& elem(int i)           { return *(type*)&graph_array(edge)::elem(i);}\
  600. void  init(const graph& G, int m, type i)\
  601.                                   { graph_array(edge)::init(G,m,Ent(i)); }\
  602. void  init(const graph& G, type i){ graph_array(edge)::init(G,Ent(i)); }\
  603. void  init(const graph& G)  { type y=0; graph_array(edge)::init(G,Ent(y)); }\
  604. void  init(const edge_array(type)& A)\
  605.                             { graph_array(edge)::init((graph_array(edge)&) A); }\
  606. \
  607. edge_array(type)()                                 {}\
  608. edge_array(type)(const graph& G)                   { init(G);   }\
  609. edge_array(type)(const graph& G, int m, type i)    { init(G,m,i); }\
  610. edge_array(type)(const graph& G, type i)           { init(G,i); }\
  611. edge_array(type)(const edge_array(type)& A)        { init(A);   }\
  612. edge_array(type)& operator=(const edge_array(type)& A) { init(A); return *this;}\
  613. \
  614. ~edge_array(type)()                { clear(); }\
  615. };
  616.  
  617. //------------------------------------------------------------------------------
  618. // node matrices
  619. //------------------------------------------------------------------------------
  620.  
  621. typedef graph_array(node)* node_array_ptr;
  622.  
  623. declare(node_array,node_array_ptr);
  624.  
  625. class Node_Matrix {
  626. graph* g;
  627. node_array(node_array_ptr) M;
  628. virtual void init_entry(ent& x)  const { x=0; }
  629. virtual void copy_entry(ent& x)  const { x=x; }
  630. virtual void clear_entry(ent& x) const { x=0; }
  631. virtual void print_entry(ent& x) const { Print(x); }
  632. public:
  633.  graph_array(node)& operator[](node v);
  634.  ent& entry(node, node);
  635.  ent  inf(node, node) const;
  636.  void clear();
  637.  void init(const graph&, int, ent);
  638.  void init(const graph&, ent);
  639.  void init(Node_Matrix&);
  640.  Node_Matrix()  {}
  641. ~Node_Matrix()  { clear(); }
  642. };
  643.  
  644.  
  645. #define node_matrix(type) name2(type,node_matrix)
  646.  
  647. #define node_matrixdeclare(type)\
  648. \
  649. class node_matrix(type): public Node_Matrix {\
  650. void copy_entry(ent& x)  const { x = Copy(*(type*)&x);  }\
  651. void clear_entry(ent& x) const { Clear(*(type*)&x); }\
  652. void init_entry(ent& x)  const { x = Copy(type(0)); }\
  653. void print_entry(ent& x) const { Print(*(type*)&x); }\
  654. public:\
  655. node_array(type)& operator[](node v)\
  656. { return *(node_array(type)*)&(Node_Matrix::operator[](v)); }\
  657. \
  658. type& operator()(node v, node w) { return *(type*)&(Node_Matrix::entry(v,w));}\
  659. type  operator()(node v, node w) const { return type(Node_Matrix::inf(v,w)); }\
  660. \
  661. void  init(const graph& G, int n, type i) { Node_Matrix::init(G,n,Ent(i)); }\
  662. void  init(const graph& G, type i)        { Node_Matrix::init(G,Ent(i)); }\
  663. void  init(const graph& G)    { type y = 0; Node_Matrix::init(G,Ent(y)); }\
  664. void  init(const node_matrix(type)& M) { Node_Matrix::init((Node_Matrix&) M); }\
  665. \
  666. node_matrix(type)() {}\
  667. node_matrix(type)(const graph& G)                 { init(G);   }\
  668. node_matrix(type)(const graph& G, int n, type x)  { init(G,n,x); }\
  669. node_matrix(type)(const graph& G, type x)         { init(G,x); }\
  670. node_matrix(type)(const node_matrix(type)& M)     { init(M); }\
  671. \
  672. node_matrix(type)& operator=(const node_matrix(type)& M){init(M);return *this;}\
  673. \
  674. ~node_matrix(type)()                 { clear();   }\
  675. };\
  676.  
  677.  
  678. //------------------------------------------------------------------------------
  679. // Iteration   (macros)
  680. //------------------------------------------------------------------------------
  681.  
  682. /*
  683. #define forall_nodes(a,b) for ((b).init_node_iterator(); (b).next_node(a); )
  684. #define forall_edges(a,b) for ((b).init_edge_iterator(); (b).next_edge(a); )
  685. */
  686.  
  687. #define forall_nodes(a,g) for (a=(g).first_node(); a; a=(g).succ_node(a) )
  688.  
  689. #define forall_edges(a,g) for (a=(g).first_edge(); a; a=(g).succ_edge(a) )
  690.  
  691. #define forall_adj_edges(a,b)\
  692. for (graph_of(b)->init_adj_iterator(b); graph_of(b)->next_adj_edge(a,b); )
  693.  
  694. /*
  695. #define forall_adj_edges(a,b)\
  696.    for (a=graph_of(b)->first_adj_edge(b); a; a=graph_of(b)->adj_succ(a) ) */
  697.  
  698.  
  699. #define forall_adj_nodes(a,b)\
  700. for (graph_of(b)->init_adj_iterator(b); graph_of(b)->next_adj_node(a,b); )
  701.  
  702. #define forall_node_pairs(a,b,g)\
  703. forall_nodes(a,g) for (b=(g).first_node(); b; b=(g).succ_node(b) )
  704.  
  705.  
  706. // reverse
  707.  
  708. #define Forall_nodes(a,g) for (a=(g).last_node(); a; a=(g).pred_node(a) )
  709.  
  710. #define Forall_edges(a,g) for (a=(g).last_edge(); a; a=(g).pred_edge(a) )
  711.  
  712.  
  713.  
  714. //-----------------------------------------------------------------------------
  715. // miscellaneous  (should be members or constructors)
  716. //-----------------------------------------------------------------------------
  717.  
  718. extern void eliminate_parallel_edges(graph& G);
  719.  
  720. extern void complete_graph(graph&,int);
  721. extern void random_graph(graph&,int,int);
  722. extern void random_planar_graph(graph&,int);
  723.  
  724. extern void test_graph(graph&);
  725. extern void test_bigraph(graph&, list(node)&, list(node)&);
  726.  
  727. #endif
  728.  
  729.